#!/usr/bin/env python3
#-*- coding:utf-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年02月24日
描    述：
'''

class Solution:
    def searchMatrix(self, matrix: 'List[List[int]]', target: 'int') -> 'bool':
        m = len(matrix)
        if m == 0:
            return False

        n = len(matrix[0])
        if n == 0:
            return False

        start = 0
        end = m*n - 1
        while start <= end:
            mid = start + (end - start)//2
            if target == matrix[mid//n][mid%n]:
                return True

            if target > matrix[mid//n][mid%n]:
                start = mid + 1
            else:
                end = mid - 1

        return False
        
